Search results for "Logic in computer science"
showing 10 items of 129 documents
De l'usage des logiques modales pour la gestion de l'incertitude des données : application en archéologie
2015
Archaeological information systems offer methods and tools for representing collected data and performing analyses with which taking into account imperfect data is often hard to please. Our contribution describes the use of several modal logics to model and verify the effects of the consideration of uncertain data, but also to check the quality of a corpus in an in-terdisciplinary collaborative environment. The modelling and the reasoning based on uncertain data, which are studied in this article, are integrated open and extensible platform allowing to manage archaeological data. From the computing point of view, the reasoner used, based on the first order logic, provides the archaeologists…
Inconsistency measuring over multisets of formulas
2018
International audience; Measuring Inconsistency in Information : The concept of measuring inconsistency in information was developed by John Grant in a 1978 paper in the context of first-order logic. For more than 20 years very little was done in this area until in the early 2000s a number of AI researchers started to formulate new inconsistency measures primarily in the context of propositional logic knowledge bases. The aim of this volume is to survey what has been done so far, to expand inconsistency measurement to other formalisms, to connect it with related topics, and to provide ideas for further research in a topic that is particularly relevant now in view of the many inconsistencies…
Subsumption-driven clause learning with DPLL+restarts
2019
We propose to use a DPLL+restart to solve SAT instances by successive simplifications based on the production of clauses that subsume the initial clauses. We show that this approach allows the refutation of pebbling formulae in polynomial time and linear space, as effectively as with a CDCL solver.
Vector description of higher-order modes in photonic crystal fibers
2000
We extensively study the propagation features of higher-order modes in a photonic crystal fiber (PCF). Our analysis is based on a full-vector modal technique specially adapted to accurately describe light propagation in PCF's. Unlike conventional fibers, PCF's exhibit a somewhat unusual mechanism for the generation of higher-order modes. Accordingly, PCF's are characterized by the constancy of the number of modes below a wavelength threshold. An explicit verification of this property is given through a complete analysis of the dispersion relations of higher-order modes in terms of the structural parameters of this kind of fiber. The transverse irradiance distributions for some of these high…
Heyting-valued interpretations for Constructive Set Theory
2006
AbstractWe define and investigate Heyting-valued interpretations for Constructive Zermelo–Frankel set theory (CZF). These interpretations provide models for CZF that are analogous to Boolean-valued models for ZF and to Heyting-valued models for IZF. Heyting-valued interpretations are defined here using set-generated frames and formal topologies. As applications of Heyting-valued interpretations, we present a relative consistency result and an independence proof.
Modal Consequence Relations Extending S4.3: An Application of Projective Unification
2016
We characterize all finitary consequence relations over $\mathbf{S4.3}$ , both syntactically, by exhibiting so-called (admissible) passive rules that extend the given logic, and semantically, by providing suitable strongly adequate classes of algebras. This is achieved by applying an earlier result stating that a modal logic $L$ extending $\mathbf{S4}$ has projective unification if and only if $L$ contains $\mathbf{S4.3}$ . In particular, we show that these consequence relations enjoy the strong finite model property, and are finitely based. In this way, we extend the known results by Bull and Fine, from logics, to consequence relations. We also show that the lattice of consequence relation…
Error-Free Affine, Unitary, and Probabilistic OBDDs
2021
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las-Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata counterparts of these models.
The Syllogistic with Unity
2011
We extend the language of the classical syllogisms with the sentence-forms “At most 1 p is a q” and “More than 1 p is a q”. We show that the resulting logic does not admit a finite set of syllogism-like rules whose associated derivation relation is sound and complete, even when reductio ad absurdum is allowed.
Monadic second-order logic over pictures and recognizability by tiling systems
1994
We show that a set of pictures (rectangular arrays of symbols) is recognized by a finite tiling system if and only if it is definable in existential monadic second-order logic. As a consequence, finite tiling systems constitute a notion of recognizability over two-dimensional inputs which at the same time generalizes finite-state recognizability over strings and matches a natural logic. The proof is based on the Ehrenfeucht-FraIsse technique for first-order logic and an implementation of “threshold counting” within tiling systems.
Error-Free Affine, Unitary, and Probabilistic OBDDs
2018
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata versions of these models.